<!DOCTYPE html>
<html class="no-js" lang="zh">
  <head>
<meta charset="utf-8">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
<link rel="alternate" href="https://www.desgard.com" hreflang="pt-BR">
<link href="http://gmpg.org/xfn/11" rel="profile">
<meta name="HandheldFriendly" content="True">
<meta name="MobileOptimized" content="320">
<meta name="theme-color" content="#005344">
<title>Guardia · 瓜地</title>
<meta name="google-site-verification" content="zS1dSn20XtA4FJYEOQLXqI0boxZdMnJ2g3beje-cl20">
<meta name="description" content="I write many code to write less code.💻">
<meta name="keywords" content="">
<!-- Social: Facebook / Open Graph -->
<meta property="og:url" content="https://www.desgard.com/autolayout-simplex/">
<meta property="og:title" content="       AutoLayout 中的线性规划 - Simplex 算法 | Gua  ">
<meta property="og:description" content="I write many code to write less code.💻">
<meta property="og:site_name" content="Desgard_Duan">
<meta property="og:locale" content="pt_BR">
<meta property="og:type" content="website">
<meta property="og:author" content="https://www.facebook.com/desgard.duan">
<meta property="og:image" content="https://www.desgard.com">
<!-- Social: Twitter -->
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:site" content="@nandomoreirame">
<meta name="twitter:domain" content="https://www.desgard.com">
<meta name="twitter:title" content="       AutoLayout 中的线性规划 - Simplex 算法 | Gua  ">
<meta name="twitter:description" content="I write many code to write less code.💻">
<meta name="twitter:image:src" content="https://www.desgard.com">
<!-- Favicons -->
<link rel="apple-touch-icon" sizes="114x114" href="https://www.desgard.com/assets/ico/apple-touch-icon-114-516f4e19976b9e4dbb77ad9b576831fe.png">
<link rel="apple-touch-icon" sizes="72x72" href="https://www.desgard.com/assets/ico/apple-touch-icon-72-5409b2df229305703caf583d86c845ab.png">
<link rel="apple-touch-icon" href="https://www.desgard.com/assets/ico/apple-touch-icon-57-aa873e019cf659e0d4e6a0b5bb9f379d.png">
<link rel="shortcut icon" href="https://www.desgard.com/assets/ico/favicon-4298be3d3fbe23e18d65bded9d930899.png">
<!-- rel prev and next -->
<!-- Canonical link tag -->
<link rel="canonical" href="https://www.desgard.com/autolayout-simplex/">
<link rel="alternate" type="application/rss+xml" title="Gua" href="https://www.desgard.com/feed.xml">
<link rel="stylesheet" href="/assets/main-0b7b828712f4c43b75bba4861c907bb1.css">
<script src="/assets/modernizr-custom-cb807611a3e262b2eac59444cbab74d6.js" data-cfasync="false"></script>
<script src="/assets/js/jquery-3.1.js"></script>
<script src="/assets/js/jquery.rotate.js"></script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="application/ld+json">
{
  "@context": "http://schema.org",
  "@type": "Website",
  "publisher": "www.desgard.com",
  "url": "http://www.desgard.com/",
  "description": "瓜地"
}
</script>
<script type="text/javascript">
  var disqus_shortname = 'desgard',
      baseurl          = '';
</script>
<!--
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-52446115-1']);
_gaq.push(['_trackPageview']);
(function() {
  var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
  ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
  var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>-->
<script>
var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "//hm.baidu.com/hm.js?c5a8123bc51782a3083a631ed9ff50e4";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script>
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ['$','$'] ],
        displayMath: [ ['$$','$$'] ],
        processEscapes: true
      }
    });
  </script>
  </head>
  <body class="post-template single">
    <header class="header">
  <div class="container">
    <h1><a href="/"><strong>desgard</strong>.com</a></h1>
    <nav class="navbar">
      <ul>
        <li><a href="/">Home</a></li>
        <li><a href="#!" data-modal="modalSearch"><i class="fa fa-search"></i></a></li>
        <li><a href="/comment " target="_blank"><i class="fa fa-comments"></i></a></li>
        <li><a href="/feed.xml" target="_blank"><i class="fa fa-feed"></i></a></li>
      </ul>
    </nav>
  </div>
</header>
    <main class="wrapper container" itemprop="mainContentOfPage" itemscope="itemscope" itemtype="http://schema.org/Blog">
      <article class="post" itemscope="itemscope" itemtype="http://schema.org/BlogPosting" itemprop="blogPost">
  <header class="post-header">
    <h1>AutoLayout 中的线性规划 - Simplex 算法</h1>
    <div class="post-meta">
      <time datetime="2015-10-13">
        <i class="fa fa-calendar-o"></i> <time datetime="2018-07-04"> 2018-07-04
      </time>
      <span>
        <i class="fa fa-comments"></i> <a href="#container">Comment me!</a>
      </span>
      <span>
<!--
        <i class="fa fa-folder-open-o"></i> 
-->
      </span>
    </div>
  </header>
  <p>前一段时间由于跳槽，博客停更了大概有 150 天左右的样子。在所有事情都安置好后，决定推掉之前写过的半截文章，开始更这么一个专题。再这之前，自己没有阅读 paper 的习惯，这也是一次对自己的挑战。</p>
<p>本文与 iOS 关系不大，多半偏向 paper 的学习和算法介绍，请读者根据兴趣自行阅读。</p>
<h2 id="section">温习线性规划</h2>
<p>当我们在 Storyboard 上建立完一堆约束后，发现其实所有的约束都可以用多个约束间的不等式关系来描述。于是乎将 UI 的布局问题，就转化成了一个<strong>线性规划问题</strong>。</p>
<p><img src="../assets/images/blog/15272074383889/15297228541122.jpg" alt="" /></p>
<p>如何求解这个线性规划问题呢？我们引入一个求解线性规划的经典方法 - <strong>Simplex 算法</strong>。虽然该算法具有指数时间的复杂度，但是在绝大多数情况下仍旧会保持着多项式时间复杂度，关于复杂度分析我们在后文具体分析。</p>
<h2 id="simplex-">Simplex 算法</h2>
<p>Simplex 算法主要有三个步骤：</p>
<ol>
  <li>找到一个初始的基本可行解；</li>
  <li>持续进行<em>旋转（Pivot）</em>操作；</li>
  <li>重复操作 2，直到找到最优解；</li>
</ol>
<p>Simplex 算法我以下面一个线性规划方程为例：</p>
<script type="math/tex; mode=display">% <![CDATA[
\begin{cases}
	\ -x_1-14x_2-6x_3 \quad min\\
	\ x_1+x_2+x_3+x_4=4&\\
	\ x_1\leq2\\
	\ x_3\leq3\\
	\ 3x_2+x_3\leq6\\
	\ x_1,x_2,x_3\geq0
\end{cases} %]]></script>
<p>改写成<strong>松弛形式</strong>：</p>
<script type="math/tex; mode=display">\begin{cases}
	\ -x_1-14x_2-6x_3 \quad min\\
	\ x_1+x_2+x_3+x_4=4 \\
	\ x_1+x_5=2 \\
	\ x_3+x_6=3 \\
	\ 3x_2+x_3+x_7=6 \\
	\ x_1, x_2, x_3, x_4, x_5, x_6, x_7 \geq 0
\end{cases}</script>
<p>将增加的松弛量放到等号左边，得到<strong>基本变量</strong>和<strong>非基本变量</strong>关系式：</p>
<script type="math/tex; mode=display">\begin{cases}
	\ \beta=-x_1-14x_2-6x_3 \\
	\ x_4=4-x_1-x_2-x_3 \\
	\ x_5=2-x_1 \\
	\ x_6=3-x_3 \\
	\ x_7=6-3x_2-x_3
\end{cases}</script>
<p>将右边所有非常量都设为 0，然后左边基本变量的值求得：</p>
<script type="math/tex; mode=display">(x_1,x_2,...,x_7)=(0,0,0,4,2,3,6)</script>
<p>此时目标值 $\beta=0$。求出基本可行解后，我们开始对其做旋转操作。每次旋转，我们选择目标函数中带有负常数项进行放大操作，此时选定 $x_1$。将 $x_1=2-x_5$ 带入非基本变量：</p>
<script type="math/tex; mode=display">\begin{cases}
	\ \beta=-2-14x_2-6x_3+x_5 \\
	\ x_4=2-x_2-x_3+x_5 \\
	\ x_5 = 2-x_1 \\
	\ x_6 = 3-x_3 \\
	\ x_7 = 6-3x_2-x_3
\end{cases}</script>
<p>每次旋转过程，一次旋转选取一个非基本变量，这里称作<strong>替入变量</strong> $x_e$ 和一个<strong>替出变量</strong> $x_i$，然后带入变量。此时继续将所有非常量为设为 0，得到：</p>
<script type="math/tex; mode=display">(x_1,x_2,...,x_7)=(2,0,0,2,0,3,6) \\
\beta = -2</script>
<p>此时我们发现目标值减少了 <code>-2</code>。继续旋转，这次我们选择 $x_2$，通过式 ② 得到 $x_2=2-x_3-x_4+x_5$ 带入得到：</p>
<script type="math/tex; mode=display">\begin{cases}
	\ \beta = -30-\frac{2}{3}x_3+x_4+\frac{13}{3}x_7 \\
	\ x_2=2-\frac{1}{3}x_3-\frac{1}{3}x_7 \\
	\ x_1=2-\frac{2}{3}x_3-x_4+\frac{1}{3}x_7 \\
	\ x_6=3-x_3 \\
	\ x_5=\frac{2}{3}x_3+x_4-\frac{1}{3}x_7
\end{cases}</script>
<p>求出解和目标值为：</p>
<script type="math/tex; mode=display">(x_1,x_2,...,x_7)=(2,2,0,0,0,3,0) \\
\beta=-2</script>
<p>发现其目标值并没有提升，之后我们做最后一次旋转，选择 $x_3$，通过式 ② 得到 $x_3=3-\frac{3}{2}x_1-\frac{3}{2}x_4-\frac{1}{2}x_7$，然后分别带入：</p>
<script type="math/tex; mode=display">\begin{cases}
	\ \beta = -32+x_1+2x_4+4x_7 \\
	\ x_2=1+\frac{1}{2}x_1+\frac{1}{2}x_4-\frac{1}{2}x_7 \\
	\ x_3=3-\frac{3}{2}x_1-\frac{3}{2}x_4+\frac{1}{2}x_7 \\
	\ x_6=\frac{3}{2}x_1+\frac{3}{2}x_4-\frac{1}{2}x_7 \\
	\ x_5=2-x_1
\end{cases}</script>
<p>现在目标函数中没有可以增大的项了，停止选装。所以 $\beta=-32$ 是我们最终的目标解。此时基本解为 $(x_1,x_2,…,x_7)=(0,1,3,0,2,0,0)$。</p>
<p>可是往往事情并不想这次的计算那么顺利，有的时候我们发现旋转操作一直无法将目标值继续扩大或缩小，也就是之前计算中的倒数第二次选装操作。这种现象叫做<strong>退化（Degeneracy）</strong>。有的时候退化现象还会产生旋转<strong>循环（cycling）</strong>，从而一直无法到最终的旋转状态。产生循环的原因在《算法导论》中有解释：</p>
<blockquote>
  <p>Degeneracy can prevent the simplex algorithm from terminating, because it can lead to a phenomenon known as cycling: the slack forms at two different iterations of SIMPLEX are identical. Because of degeneracy, SIMPLEX could choose a sequence of pivot operations that leave the objective value unchanged but repeat a slack form within the sequence. Since SIMPLEX is a deterministic algorithm, if it cycles, then it will cycle through the same series of slack forms forever, never terminating.</p>
</blockquote>
<p>简单的来表述，其实是因为 Simplex 算法自身的原因，可能会产生不同的旋转迭代过程中，松弛形式相同，从而无法缩减目标值，并构成循环条件。</p>
<p>避免退化的方法就是使用 <strong>Bland 规则</strong>：在选择带入变量和替出变脸的时候，选择满足下列条件的最小值：</p>
<ol>
  <li>带入变量 $x_e$：目标条件中，系数为负数的第一个作为带入变量；</li>
  <li>替出变量 $x_i$：对所有约束条件中，选择对 $x_e$ 约束强度最大的一式；</li>
</ol>
<h2 id="simplex--coding-">Simplex 算法 Coding 及改善</h2>
<p>拿出最开始的线性规划方程组（松弛形式）：</p>
<script type="math/tex; mode=display">\begin{cases}
	\ -x_1-14x_2-6x_3 \quad min\\
	\ x_1+x_2+x_3+x_4=4 \\
	\ x_1+x_5=2 \\
	\ x_3+x_6=3 \\
	\ 3x_2+x_3+x_7=6 \\
	\ x_1, x_2, x_3, x_4, x_5, x_6, x_7 \geq 0
\end{cases}</script>
<p>用三个矩阵来表达这个松弛形式：</p>
<script type="math/tex; mode=display">% <![CDATA[
C =
\left\{
	\begin{matrix}
		-1 & -14 & -6 & 0 & 0 & 0 & 0 \\
	\end{matrix}
\right\} %]]></script>
<script type="math/tex; mode=display">B = 
\left\{
	\begin{matrix}
		4 \\
		2 \\
		3 \\
		6 
	\end{matrix}
\right\}</script>
<script type="math/tex; mode=display">% <![CDATA[
A = 
\left\{
	\begin{matrix}
		1 & 1 & 1 & 1 & 0 & 0 & 0 \\
		1 & 0 & 0 & 0 & 1 & 0 & 0 \\
		0 & 0 & 1 & 0 & 0 & 1 & 0 \\
		0 & 3 & 1 & 0 & 0 & 0 & 1  
	\end{matrix}
\right\} %]]></script>
<ul>
  <li>矩阵 A：约束条件的系数矩阵；</li>
  <li>矩阵 B：约束条件值矩阵；</li>
  <li>矩阵 C：目标函数系数矩阵；</li>
</ul>
<p>把这三个矩阵拼接起来：</p>
<script type="math/tex; mode=display">% <![CDATA[
S_1 = 
\left\{
\begin{matrix}
	0 & -1 & -14 & -6 & 0 & 0 & 0 & 0 \\
	4 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\
	2 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\
	3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\
	6 & 0 & 3 & 1 & 0 & 0 & 0 & 1  
\end{matrix}
\right\} %]]></script>
<p>然后我们拿出第一次旋转后的约束方程：</p>
<script type="math/tex; mode=display">\begin{cases}
	\ \beta=-2-14x_2-6x_3+x_5 \\
	\ x_4=2-x_2-x_3+x_5 \\
	\ x_5 = 2-x_1 \\
	\ x_6 = 3-x_3 \\
	\ x_7 = 6-3x_2-x_3
\end{cases}</script>
<p>整理后获得矩阵：</p>
<script type="math/tex; mode=display">% <![CDATA[
S_2 =
\left\{
\begin{matrix}
	2 & 0 & -14 & -6 & 0 & 1 & 0 & 0 \\
	2 & 0 &  1  & 1 & 1 & -1 & 0 & 0 \\
	2 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\
	3 & 0 & 0 & 1 & 0 & 0& 1 & 0 \\
	6 & 0 & 3 & 1 & 0 & 0 & 0 & 1 \\
\end{matrix}
\right\} %]]></script>
<p>在这一步中，我们选择了将 $x_1$ 用 $x_5$ 表示。矩阵变换由于 $x_1$ 是被替换量。</p>
<p>第三行中，我们需要的是将选用量的系数归一。所以该行只要进行 <code>matrix[2] /= matrix[2][1]</code> 即可。</p>
<p>我们推导一下非第三行的变换规律。$x_1=2-x_5$，得到第 i 行的系数 <code>matrix[i - 1] = matrix[i - 1] - matrix[2] * matrix[i - 1][1]</code>。我们发现还原操作最后变成了两行相减。</p>
<p>对于目标函数，与非第三行进行同样的操作即可。通过这个思路写出代码：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="n">import</span> <span class="n">numpy</span> <span class="n">as</span> <span class="n">np</span>
<span class="k">class</span> <span class="nc">Simplex</span><span class="p">(</span><span class="n">object</span><span class="p">):</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="nb">self</span><span class="p">,</span> <span class="n">obj</span><span class="p">,</span> <span class="n">max_mode</span><span class="o">=</span><span class="no">False</span><span class="p">):</span>
        <span class="c1"># 默认是解决 min LP 问题，如果是最大值用 True，要 mut -1</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">max_mode</span> <span class="o">=</span> <span class="n">max_mode</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">mat</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">array</span><span class="p">(</span><span class="o">[[</span><span class="mi">0</span><span class="o">]</span> <span class="o">+</span> <span class="n">obj</span><span class="o">]</span><span class="p">)</span> <span class="o">*</span> <span class="p">(</span><span class="o">-</span><span class="mi">1</span> <span class="k">if</span> <span class="n">max_mode</span> <span class="k">else</span> <span class="mi">1</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">add_constraint</span><span class="p">(</span><span class="nb">self</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">):</span>
        <span class="c1"># 增加约束，即在矩阵最后一行增加</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">mat</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">vstack</span><span class="p">(</span><span class="o">[</span><span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="p">,</span> <span class="o">[</span><span class="n">b</span><span class="o">]</span> <span class="o">+</span> <span class="n">a</span><span class="o">]</span><span class="p">)</span>
    <span class="vi">@property</span>
    <span class="k">def</span> <span class="nf">solve</span><span class="p">(</span><span class="nb">self</span><span class="p">):</span>
        <span class="c1"># 获得矩阵的纬度</span>
        <span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="o">.</span><span class="n">shape</span>
        <span class="c1"># 零矩阵和对角矩阵上下排列</span>
        <span class="n">temp</span><span class="p">,</span> <span class="n">B</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">vstack</span><span class="p">(</span><span class="o">[</span><span class="n">np</span><span class="o">.</span><span class="n">zeros</span><span class="p">((</span><span class="mi">1</span><span class="p">,</span> <span class="n">m</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)),</span> <span class="n">np</span><span class="o">.</span><span class="n">eye</span><span class="p">(</span><span class="n">m</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span><span class="o">]</span><span class="p">),</span> <span class="n">list</span><span class="p">(</span><span class="n">range</span><span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">n</span> <span class="o">+</span> <span class="n">m</span> <span class="o">-</span> <span class="mi">1</span><span class="p">))</span>
        <span class="c1"># 组合系数矩阵</span>
        <span class="n">mat</span> <span class="o">=</span> <span class="nb">self</span><span class="o">.</span><span class="n">mat</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">hstack</span><span class="p">(</span><span class="o">[</span><span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="p">,</span> <span class="n">temp</span><span class="o">]</span><span class="p">)</span>
        <span class="c1"># 循环所有目标函数的系数,直到全部没有负数为止</span>
        <span class="k">while</span> <span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">:</span><span class="o">].</span><span class="n">min</span><span class="p">()</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">:</span>
            <span class="c1"># 1. 选择合适的替入和替出变量</span>
            <span class="c1"># Bland 规则对矩阵做退化操</span>
            <span class="n">col</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">where</span><span class="p">(</span><span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">:</span><span class="o">]</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span><span class="o">[</span><span class="mi">0</span><span class="o">][</span><span class="mi">0</span><span class="o">]</span> <span class="o">+</span> <span class="mi">1</span>
            <span class="n">row</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">array</span><span class="p">(</span><span class="o">[</span><span class="n">mat</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="mi">0</span><span class="o">]</span> <span class="o">/</span> <span class="n">mat</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="n">col</span><span class="o">]</span> <span class="k">if</span> <span class="n">mat</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="n">col</span><span class="o">]</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="k">else</span> <span class="mh">0x7fffffff</span> <span class="k">for</span> <span class="n">i</span> <span class="k">in</span>
                            <span class="n">range</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">mat</span><span class="o">.</span><span class="n">shape</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span><span class="p">)</span><span class="o">]</span><span class="p">)</span><span class="o">.</span><span class="n">argmin</span><span class="p">()</span> <span class="o">+</span> <span class="mi">1</span>  <span class="c1"># find the theta index</span>
            <span class="c1"># 如果没有替出变量,则说明原问题无界</span>
            <span class="k">if</span> <span class="n">mat</span><span class="o">[</span><span class="n">row</span><span class="o">][</span><span class="n">col</span><span class="o">]</span> <span class="o">&lt;=</span> <span class="mi">0</span><span class="p">:</span> <span class="k">return</span> <span class="no">None</span>
            <span class="c1"># 2. 旋转过程</span>
            <span class="c1"># 系数归一,整行相除</span>
            <span class="n">mat</span><span class="o">[</span><span class="n">row</span><span class="o">]</span> <span class="o">/=</span> <span class="n">mat</span><span class="o">[</span><span class="n">row</span><span class="o">][</span><span class="n">col</span><span class="o">]</span>
            <span class="c1"># 对所有 i!= row 进行 mat[i]= mat[i] - mat[row] * mat[i][col] 操作</span>
            <span class="n">ids</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">arange</span><span class="p">(</span><span class="n">mat</span><span class="o">.</span><span class="n">shape</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span><span class="p">)</span> <span class="o">!=</span> <span class="n">row</span>
            <span class="n">mat</span><span class="o">[</span><span class="n">ids</span><span class="o">]</span> <span class="o">-=</span> <span class="n">mat</span><span class="o">[</span><span class="n">row</span><span class="o">]</span> <span class="o">*</span> <span class="n">mat</span><span class="o">[</span><span class="n">ids</span><span class="p">,</span> <span class="ss">col</span><span class="p">:</span><span class="n">col</span> <span class="o">+</span> <span class="mi">1</span><span class="o">]</span>
            <span class="n">B</span><span class="o">[</span><span class="n">row</span><span class="o">]</span> <span class="o">=</span> <span class="n">col</span>
        <span class="c1"># 返回目标值,若为最小值,则要 * -1,最大值则不用。</span>
        <span class="c1"># 后面的矩阵是各个解的系数矩阵,基本变量对应 bi,非基本变量为0</span>
        <span class="c1"># B[i] &lt; n 判断即为删除松弛增加的变量</span>
        <span class="k">return</span> <span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="o">][</span><span class="mi">0</span><span class="o">]</span> <span class="o">*</span> <span class="p">(</span><span class="mi">1</span> <span class="k">if</span> <span class="nb">self</span><span class="o">.</span><span class="n">max_mode</span> <span class="k">else</span> <span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="p">{</span><span class="n">B</span><span class="o">[</span><span class="n">i</span><span class="o">]</span><span class="p">:</span> <span class="n">mat</span><span class="o">[</span><span class="n">i</span><span class="p">,</span> <span class="mi">0</span><span class="o">]</span> <span class="k">for</span> <span class="n">i</span> <span class="k">in</span> <span class="n">range</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">m</span><span class="p">)</span> <span class="k">if</span> <span class="n">B</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">}</span>
<span class="k">if</span> <span class="n">__name__</span> <span class="o">==</span> <span class="s1">&#39;__main__&#39;</span><span class="p">:</span>
    <span class="n">t</span> <span class="o">=</span> <span class="no">Simplex</span><span class="p">(</span><span class="o">[-</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">14</span><span class="p">,</span> <span class="o">-</span><span class="mi">6</span><span class="o">]</span><span class="p">)</span>
    <span class="n">t</span><span class="o">.</span><span class="n">add_constraint</span><span class="p">(</span><span class="o">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="o">]</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span>
    <span class="n">t</span><span class="o">.</span><span class="n">add_constraint</span><span class="p">(</span><span class="o">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="o">]</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span>
    <span class="n">t</span><span class="o">.</span><span class="n">add_constraint</span><span class="p">(</span><span class="o">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="o">]</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span>
    <span class="n">t</span><span class="o">.</span><span class="n">add_constraint</span><span class="p">(</span><span class="o">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">1</span><span class="o">]</span><span class="p">,</span> <span class="mi">6</span><span class="p">)</span>
    <span class="nb">print</span><span class="p">(</span><span class="n">t</span><span class="o">.</span><span class="n">solve</span><span class="p">)</span>
    <span class="nb">print</span><span class="p">(</span><span class="n">t</span><span class="o">.</span><span class="n">mat</span><span class="p">)</span>
<span class="s1">&#39;&#39;&#39;</span>
<span class="s1">(-32.0, {2: 1.0, 3: 3.0})</span>
<span class="s1">[[32.   1.   0.   0.   2.   0.   0.   4. ]</span>
<span class="s1"> [ 1.  -0.5  1.   0.  -0.5  0.   0.   0.5]</span>
<span class="s1"> [ 3.   1.5  0.   1.   1.5  0.   0.  -0.5]</span>
<span class="s1"> [ 0.  -1.5  0.   0.  -1.5  0.   1.   0.5]</span>
<span class="s1"> [ 2.   1.   0.   0.   0.   1.   0.   0. ]]</span>
<span class="s1">&#39;&#39;&#39;</span></code></pre></div>
<h2 id="section-1">算法再修正</h2>
<p>给出这么一个测试用例：</p>
<script type="math/tex; mode=display">\begin{cases}
	\ x_1+2x_2 \quad min\\
	\ x_1+x_2\leq2\\
	\ x_1+x_2\geq1\\
	\ x_1,x_2\geq0
\end{cases}</script>
<p>使用上述算法带入：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="k">if</span> <span class="n">__name__</span> <span class="o">==</span> <span class="s1">&#39;__main__&#39;</span><span class="p">:</span>
    <span class="n">t</span> <span class="o">=</span> <span class="no">Simplex</span><span class="p">(</span><span class="o">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="o">]</span><span class="p">)</span>
    <span class="n">t</span><span class="o">.</span><span class="n">add_constraint</span><span class="p">(</span><span class="o">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="o">]</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span>
    <span class="n">t</span><span class="o">.</span><span class="n">add_constraint</span><span class="p">(</span><span class="o">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="o">]</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span>
    <span class="nb">print</span><span class="p">(</span><span class="n">t</span><span class="o">.</span><span class="n">solve</span><span class="p">)</span>
    <span class="nb">print</span><span class="p">(</span><span class="n">t</span><span class="o">.</span><span class="n">mat</span><span class="p">)</span>
<span class="s1">&#39;&#39;&#39;</span>
<span class="s1">(-0.0, {})</span>
<span class="s1">[[0. 1. 2. 0. 0.]</span>
<span class="s1"> [2. 1. 1. 1. 0.]</span>
<span class="s1"> [1. 1. 1. 0. 1.]]</span>
<span class="s1">&#39;&#39;&#39;</span></code></pre></div>
<p>由于 <code>c &gt;= 0</code> 造成 <code>solve</code> 方法直接不迭代。我们用 GLPK 来求解一下该问题：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="n">var</span> <span class="n">x1</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span>
<span class="n">var</span> <span class="n">x2</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span>
<span class="n">minimize</span> <span class="ss">obj</span><span class="p">:</span> <span class="n">x1</span> <span class="o">+</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">x2</span><span class="p">;</span>
<span class="ss">c1</span><span class="p">:</span> <span class="n">x1</span> <span class="o">+</span> <span class="n">x2</span> <span class="o">&lt;=</span> <span class="mi">2</span><span class="p">;</span>
<span class="ss">c2</span><span class="p">:</span> <span class="n">x1</span> <span class="o">+</span> <span class="n">x2</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="p">;</span>
<span class="n">solve</span><span class="p">;</span>
<span class="nb">display</span> <span class="n">x1</span><span class="p">;</span>
<span class="nb">display</span> <span class="n">x2</span><span class="p">;</span>
<span class="k">end</span><span class="p">;</span></code></pre></div>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="ss">A</span><span class="p">:</span> <span class="n">min</span><span class="o">|</span><span class="n">aij</span><span class="o">|</span> <span class="o">=</span>  <span class="mi">1</span><span class="o">.</span><span class="mo">000</span><span class="n">e</span><span class="o">+</span><span class="mo">00</span>  <span class="n">max</span><span class="o">|</span><span class="n">aij</span><span class="o">|</span> <span class="o">=</span>  <span class="mi">1</span><span class="o">.</span><span class="mo">000</span><span class="n">e</span><span class="o">+</span><span class="mo">00</span>  <span class="n">ratio</span> <span class="o">=</span>  <span class="mi">1</span><span class="o">.</span><span class="mo">000</span><span class="n">e</span><span class="o">+</span><span class="mo">00</span>
<span class="no">Problem</span> <span class="n">data</span> <span class="n">seem</span> <span class="n">to</span> <span class="n">be</span> <span class="n">well</span> <span class="n">scaled</span>
<span class="no">Constructing</span> <span class="n">initial</span> <span class="n">basis</span><span class="o">.</span><span class="n">.</span><span class="o">.</span>
<span class="no">Size</span> <span class="n">of</span> <span class="n">triangular</span> <span class="n">part</span> <span class="n">is</span> <span class="mi">2</span>
      <span class="mi">0</span><span class="p">:</span> <span class="n">obj</span> <span class="o">=</span>   <span class="mi">0</span><span class="o">.</span><span class="mo">000000000</span><span class="n">e</span><span class="o">+</span><span class="mo">00</span> <span class="n">inf</span> <span class="o">=</span>   <span class="mi">1</span><span class="o">.</span><span class="mo">000</span><span class="n">e</span><span class="o">+</span><span class="mo">00</span> <span class="p">(</span><span class="mi">1</span><span class="p">)</span>
      <span class="mi">1</span><span class="p">:</span> <span class="n">obj</span> <span class="o">=</span>   <span class="mi">1</span><span class="o">.</span><span class="mo">000000000</span><span class="n">e</span><span class="o">+</span><span class="mo">00</span> <span class="n">inf</span> <span class="o">=</span>   <span class="mi">0</span><span class="o">.</span><span class="mo">000</span><span class="n">e</span><span class="o">+</span><span class="mo">00</span> <span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="no">OPTIMAL</span> <span class="no">LP</span> <span class="no">SOLUTION</span> <span class="no">FOUND</span>
<span class="no">Time</span> <span class="ss">used</span><span class="p">:</span>   <span class="mi">0</span><span class="o">.</span><span class="mi">0</span> <span class="n">secs</span>
<span class="no">Memory</span> <span class="ss">used</span><span class="p">:</span> <span class="mi">0</span><span class="o">.</span><span class="mi">1</span> <span class="no">Mb</span> <span class="p">(</span><span class="mi">102205</span> <span class="n">bytes</span><span class="p">)</span>
<span class="no">Display</span> <span class="n">statement</span> <span class="n">at</span> <span class="n">line</span> <span class="mi">10</span>
<span class="n">x1</span><span class="o">.</span><span class="n">val</span> <span class="o">=</span> <span class="mi">1</span>
<span class="no">Display</span> <span class="n">statement</span> <span class="n">at</span> <span class="n">line</span> <span class="mi">11</span>
<span class="n">x2</span><span class="o">.</span><span class="n">val</span> <span class="o">=</span> <span class="mi">0</span>
<span class="no">Model</span> <span class="n">has</span> <span class="n">been</span> <span class="n">successfully</span> <span class="n">processed</span></code></pre></div>
<p>得出目标值为 <code>1</code>，解集 $(x_1, x_2)=(1, 0)$。答案是明显不一致的。</p>
<p>追溯一下原因。在之前的做法中，在第一步我们将所有的待求量设为 0 从而获得了初始解作为第一次旋转的基本可行解。这个步骤是否可行能？同样的我们带入到其松弛形式，发现 $x_3=-2$ 是不满足条件的，所以初始解是不能作为第一组基本可行解。</p>
<p>所以如果存在 $b_i&lt;0$ 的情况，就需要重新进行初始化操作，并返回一个基本可行解。我们引入构造<strong>辅助线性规划（Auxiliary Linary program）</strong>。具体的辅助线性规划其实就是引入一个$x_0$，对其进行最大化操作以测试用例为例：</p>
<script type="math/tex; mode=display">% <![CDATA[
\begin{cases}
	\ x_0 \quad min\\
	\ x_1+x_2-x_0 &\leq2\\
	\ -x_1-x_2-x_0 &\leq-1\\
	\ x_1,x_2,x_0 &\geq0
\end{cases} %]]></script>
<p>转换成松弛形式：</p>
<script type="math/tex; mode=display">% <![CDATA[
\begin{cases}
	& z = x_0 \\ 
	&x_3 = 2 – x_1 – x_2 + x_0 \\ 
	&x_4 = -1 + x_1 + x_2 + x_0\\ 
	&x_1, \quad x_2,\quad x_3,\quad x_4,\quad x_0 &\geq{0} &\\ 
\end{cases} %]]></script>
<p>这时我们可以发现我们可以将引入的 $x_0$ 当做替入变量做一次旋转，得到新式。进而通过再次旋转分别求出最终解。</p>
<script type="math/tex; mode=display">% <![CDATA[
\begin{alignat}{2} 
&z = 1 – x_1 – x_2 + x_4\\ 
&x_3 = 2 – x_1 – x_2 + x_0 \\ 
&x_0 = 1 – x_1 – x_2 + x_4\\ 
\end{alignat} %]]></script>
<p>我们总结一下这个流程：</p>
<ol>
  <li>若 $b_i$ 都为非负数。则直接使用原来的 <em>Simplex</em> 方法进行求解；</li>
  <li>否则引入 $x_0$，创建辅助线性规划 $L_aux$；</li>
  <li>松弛形式，选择 $b_i$ 最小项的那行带入，$x_0$ 作为替入变量进行一次旋转；</li>
  <li>求解 $L_aux$，若最优解为 0，说明有解。否则直接退出；</li>
  <li>$x_0$ 为基本解，继续旋转，使其成为非基本变量；</li>
  <li>恢复原始目标函数，替换变量；</li>
  <li>使用原来的 <em>Simplex</em> 求解；</li>
</ol>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="k">class</span> <span class="nc">Simplex</span><span class="p">(</span><span class="n">object</span><span class="p">):</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="nb">self</span><span class="p">,</span> <span class="n">obj</span><span class="p">,</span> <span class="n">max_mode</span><span class="o">=</span><span class="no">False</span><span class="p">):</span>
        <span class="c1"># 默认是解决 min LP 问题，如果是最大值用 True，要 mut -1</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="p">,</span> <span class="nb">self</span><span class="o">.</span><span class="n">max_mode</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">array</span><span class="p">(</span><span class="o">[[</span><span class="mi">0</span><span class="o">]</span> <span class="o">+</span> <span class="n">obj</span><span class="o">]</span><span class="p">)</span> <span class="o">*</span> <span class="p">(</span><span class="o">-</span><span class="mi">1</span> <span class="k">if</span> <span class="n">max_mode</span> <span class="k">else</span> <span class="mi">1</span><span class="p">),</span> <span class="n">max_mode</span>
    <span class="c1"># 增加约束</span>
    <span class="k">def</span> <span class="nf">add_constraint</span><span class="p">(</span><span class="nb">self</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">):</span>
        <span class="c1"># 增加约束，即在矩阵最后一行增加</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">mat</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">vstack</span><span class="p">(</span><span class="o">[</span><span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="p">,</span> <span class="o">[</span><span class="n">b</span><span class="o">]</span> <span class="o">+</span> <span class="n">a</span><span class="o">]</span><span class="p">)</span>
    <span class="c1"># Simplex 算法过程</span>
    <span class="k">def</span> <span class="nf">_simplex</span><span class="p">(</span><span class="nb">self</span><span class="p">,</span> <span class="n">mat</span><span class="p">,</span> <span class="n">B</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
        <span class="k">while</span> <span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">:</span><span class="o">].</span><span class="n">min</span><span class="p">()</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">:</span>
            <span class="c1"># Bland 规则对矩阵做退化操</span>
            <span class="n">col</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">where</span><span class="p">(</span><span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">:</span><span class="o">]</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span><span class="o">[</span><span class="mi">0</span><span class="o">][</span><span class="mi">0</span><span class="o">]</span> <span class="o">+</span> <span class="mi">1</span>
            <span class="n">row</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">array</span><span class="p">(</span><span class="o">[</span><span class="n">mat</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="mi">0</span><span class="o">]</span> <span class="o">/</span> <span class="n">mat</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="n">col</span><span class="o">]</span> <span class="k">if</span> <span class="n">mat</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="n">col</span><span class="o">]</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="k">else</span> <span class="mh">0x7fffffff</span> <span class="k">for</span> <span class="n">i</span> <span class="k">in</span>
                            <span class="n">range</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">mat</span><span class="o">.</span><span class="n">shape</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span><span class="p">)</span><span class="o">]</span><span class="p">)</span><span class="o">.</span><span class="n">argmin</span><span class="p">()</span> <span class="o">+</span> <span class="mi">1</span>
            <span class="c1"># 如果没有替出变量,则说明原问题无界</span>
            <span class="k">if</span> <span class="n">mat</span><span class="o">[</span><span class="n">row</span><span class="o">][</span><span class="n">col</span><span class="o">]</span> <span class="o">&lt;=</span> <span class="mi">0</span><span class="p">:</span> <span class="k">return</span> <span class="no">None</span>  <span class="c1"># the theta is ∞, the problem is unbounded</span>
            <span class="nb">self</span><span class="o">.</span><span class="n">_pivot</span><span class="p">(</span><span class="n">mat</span><span class="p">,</span> <span class="n">B</span><span class="p">,</span> <span class="n">row</span><span class="p">,</span> <span class="n">col</span><span class="p">)</span>
        <span class="c1"># 返回目标值,若为最小值,则要 * -1,最大值则不用。</span>
        <span class="c1"># 后面的矩阵是各个解的系数矩阵,基本变量对应 bi,非基本变量为0</span>
        <span class="c1"># B[i] &lt; n 判断即为删除松弛增加的变量</span>
        <span class="k">return</span> <span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="o">][</span><span class="mi">0</span><span class="o">]</span> <span class="o">*</span> <span class="p">(</span><span class="mi">1</span> <span class="k">if</span> <span class="nb">self</span><span class="o">.</span><span class="n">max_mode</span> <span class="k">else</span> <span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="p">{</span><span class="n">B</span><span class="o">[</span><span class="n">i</span><span class="o">]</span><span class="p">:</span> <span class="n">mat</span><span class="o">[</span><span class="n">i</span><span class="p">,</span> <span class="mi">0</span><span class="o">]</span> <span class="k">for</span> <span class="n">i</span> <span class="k">in</span> <span class="n">range</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">m</span><span class="p">)</span> <span class="k">if</span> <span class="n">B</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">}</span>
    <span class="c1"># 旋转过程</span>
    <span class="k">def</span> <span class="nf">_pivot</span><span class="p">(</span><span class="nb">self</span><span class="p">,</span> <span class="n">mat</span><span class="p">,</span> <span class="n">B</span><span class="p">,</span> <span class="n">row</span><span class="p">,</span> <span class="n">col</span><span class="p">):</span>
        <span class="c1"># 对所有 i!= row 进行 mat[i]= mat[i] - mat[row] * mat[i][col] 操作</span>
        <span class="n">mat</span><span class="o">[</span><span class="n">row</span><span class="o">]</span> <span class="o">/=</span> <span class="n">mat</span><span class="o">[</span><span class="n">row</span><span class="o">][</span><span class="n">col</span><span class="o">]</span>
        <span class="n">ids</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">arange</span><span class="p">(</span><span class="n">mat</span><span class="o">.</span><span class="n">shape</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span><span class="p">)</span> <span class="o">!=</span> <span class="n">row</span>
        <span class="n">mat</span><span class="o">[</span><span class="n">ids</span><span class="o">]</span> <span class="o">-=</span> <span class="n">mat</span><span class="o">[</span><span class="n">row</span><span class="o">]</span> <span class="o">*</span> <span class="n">mat</span><span class="o">[</span><span class="n">ids</span><span class="p">,</span> <span class="ss">col</span><span class="p">:</span><span class="n">col</span> <span class="o">+</span> <span class="mi">1</span><span class="o">]</span>
        <span class="n">B</span><span class="o">[</span><span class="n">row</span><span class="o">]</span> <span class="o">=</span> <span class="n">col</span>
    <span class="k">def</span> <span class="nf">solve</span><span class="p">(</span><span class="nb">self</span><span class="p">):</span>
        <span class="c1"># 获得矩阵的纬度</span>
        <span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="o">.</span><span class="n">shape</span>
        <span class="c1"># 组合系数矩阵</span>
        <span class="n">temp</span><span class="p">,</span> <span class="n">B</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">vstack</span><span class="p">(</span><span class="o">[</span><span class="n">np</span><span class="o">.</span><span class="n">zeros</span><span class="p">((</span><span class="mi">1</span><span class="p">,</span> <span class="n">m</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)),</span> <span class="n">np</span><span class="o">.</span><span class="n">eye</span><span class="p">(</span><span class="n">m</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span><span class="o">]</span><span class="p">),</span> <span class="n">list</span><span class="p">(</span><span class="n">range</span><span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">n</span> <span class="o">+</span> <span class="n">m</span> <span class="o">-</span> <span class="mi">1</span><span class="p">))</span>
        <span class="c1"># 循环所有目标函数的系数,直到全部没有负数为止</span>
        <span class="n">mat</span> <span class="o">=</span> <span class="nb">self</span><span class="o">.</span><span class="n">mat</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">hstack</span><span class="p">(</span><span class="o">[</span><span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="p">,</span> <span class="n">temp</span><span class="o">]</span><span class="p">)</span>  <span class="c1"># combine them!</span>
        <span class="c1"># 判断最小的常数 b 是否存在小于 0 的情况,有的话则初始解不可行</span>
        <span class="k">if</span> <span class="n">mat</span><span class="o">[</span><span class="mi">1</span><span class="p">:,</span> <span class="mi">0</span><span class="o">].</span><span class="n">min</span><span class="p">()</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">:</span>
            <span class="c1"># 找到最小 b 的那一列</span>
            <span class="n">row</span> <span class="o">=</span> <span class="n">mat</span><span class="o">[</span><span class="mi">1</span><span class="p">:,</span> <span class="mi">0</span><span class="o">].</span><span class="n">argmin</span><span class="p">()</span> <span class="o">+</span> <span class="mi">1</span>
            <span class="c1"># temp 保存原先的目标函数, 第0行设置为0</span>
            <span class="n">temp</span><span class="p">,</span> <span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">copy</span><span class="p">(</span><span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span><span class="p">),</span> <span class="mi">0</span>
            <span class="c1"># 添加 x0 需要拼接的矩阵,构造辅助线性规划</span>
            <span class="n">mat</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">hstack</span><span class="p">(</span><span class="o">[</span><span class="n">mat</span><span class="p">,</span> <span class="n">np</span><span class="o">.</span><span class="n">array</span><span class="p">(</span><span class="o">[</span><span class="mi">1</span><span class="o">]</span> <span class="o">+</span> <span class="o">[-</span><span class="mi">1</span><span class="o">]</span> <span class="o">*</span> <span class="p">(</span><span class="n">m</span> <span class="o">-</span> <span class="mi">1</span><span class="p">))</span><span class="o">.</span><span class="n">reshape</span><span class="p">((</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">))</span><span class="o">]</span><span class="p">)</span>
            <span class="c1"># 执行一次旋转操作,将系数b最小的那一项替出</span>
            <span class="nb">self</span><span class="o">.</span><span class="n">_pivot</span><span class="p">(</span><span class="n">mat</span><span class="p">,</span> <span class="n">B</span><span class="p">,</span> <span class="n">row</span><span class="p">,</span> <span class="n">mat</span><span class="o">.</span><span class="n">shape</span><span class="o">[</span><span class="mi">1</span><span class="o">]</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span>
            <span class="c1"># 求解辅助线性规划,如果最优值为0,则有解,否则无解</span>
            <span class="k">if</span> <span class="nb">self</span><span class="o">.</span><span class="n">_simplex</span><span class="p">(</span><span class="n">mat</span><span class="p">,</span> <span class="n">B</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">n</span><span class="p">)</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">:</span> <span class="k">return</span> <span class="no">None</span>
            <span class="c1"># 若x0是基本解,需要将 x0 替出</span>
            <span class="k">if</span> <span class="n">mat</span><span class="o">.</span><span class="n">shape</span><span class="o">[</span><span class="mi">1</span><span class="o">]</span> <span class="o">-</span> <span class="mi">1</span> <span class="k">in</span> <span class="ss">B</span><span class="p">:</span>
                <span class="c1"># 增加一次旋转来替出 x0</span>
                <span class="nb">self</span><span class="o">.</span><span class="n">_pivot</span><span class="p">(</span><span class="n">mat</span><span class="p">,</span> <span class="n">B</span><span class="p">,</span> <span class="n">B</span><span class="o">.</span><span class="n">index</span><span class="p">(</span><span class="n">mat</span><span class="o">.</span><span class="n">shape</span><span class="o">[</span><span class="mi">1</span><span class="o">]</span> <span class="o">-</span> <span class="mi">1</span><span class="p">),</span> <span class="n">np</span><span class="o">.</span><span class="n">where</span><span class="p">(</span><span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">:</span><span class="o">]</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">)</span><span class="o">[</span><span class="mi">0</span><span class="o">][</span><span class="mi">0</span><span class="o">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
            <span class="c1"># 恢复目标函数</span>
            <span class="nb">self</span><span class="o">.</span><span class="n">mat</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">vstack</span><span class="p">(</span><span class="o">[</span><span class="n">temp</span><span class="p">,</span> <span class="n">mat</span><span class="o">[</span><span class="mi">1</span><span class="p">:,</span> <span class="ss">:-</span><span class="mi">1</span><span class="o">]]</span><span class="p">)</span> 
            <span class="k">for</span> <span class="n">i</span><span class="p">,</span> <span class="n">x</span> <span class="k">in</span> <span class="n">enumerate</span><span class="p">(</span><span class="n">B</span><span class="o">[</span><span class="mi">1</span><span class="p">:</span><span class="o">]</span><span class="p">):</span>
                <span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span> <span class="o">-=</span> <span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="o">[</span><span class="mi">0</span><span class="p">,</span> <span class="n">x</span><span class="o">]</span> <span class="o">*</span> <span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="o">[</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="o">]</span>
        <span class="k">return</span> <span class="nb">self</span><span class="o">.</span><span class="n">_simplex</span><span class="p">(</span><span class="nb">self</span><span class="o">.</span><span class="n">mat</span><span class="p">,</span> <span class="n">B</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">n</span><span class="p">)</span></code></pre></div>
<h2 id="section-2">一个简单的场景</h2>
<p><img src="../assets/images/blog/15272074383889/15305805997704.jpg" alt="" /></p>
<p>图中是两个 <code>UIView</code> 红色和绿色是我们已经设置好的 AutoLayout 约束。我们根据约束条件，得到下列线性规划方程：</p>
<script type="math/tex; mode=display">\begin{cases}
	\ 50+x_1+25+x_2+50\leq375 \\
	\ x_1\geq50
\end{cases}</script>
<p>根据线性规划整理一下方程：</p>
<script type="math/tex; mode=display">% <![CDATA[
\begin{cases}
    \ x_2 \quad max \\
    \ x_1+x_2&\leq250 \\
    \ -x_1&\leq-50
\end{cases} %]]></script>
<p>使用我们的 Simplex 算法按照要求带入求得 $x=200$:</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="n">t</span> <span class="o">=</span> <span class="no">Simplex</span><span class="p">(</span><span class="o">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="o">]</span><span class="p">,</span> <span class="n">max_mode</span><span class="o">=</span><span class="no">True</span><span class="p">)</span>
<span class="n">t</span><span class="o">.</span><span class="n">add_constraint</span><span class="p">(</span><span class="o">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="o">]</span><span class="p">,</span> <span class="mi">250</span><span class="p">)</span>
<span class="n">t</span><span class="o">.</span><span class="n">add_constraint</span><span class="p">(</span><span class="o">[-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="o">]</span><span class="p">,</span> <span class="o">-</span><span class="mi">50</span><span class="p">)</span>
<span class="nb">print</span><span class="p">(</span><span class="n">t</span><span class="o">.</span><span class="n">solve</span><span class="p">())</span>
<span class="nb">print</span><span class="p">(</span><span class="n">t</span><span class="o">.</span><span class="n">mat</span><span class="p">)</span>
<span class="s1">&#39;&#39;&#39;</span>
<span class="s1">(200.0, {2: 200.0, 1: 50.0})</span>
<span class="s1">[[200.   0.   0.   1.   1.]</span>
<span class="s1"> [200.   0.   1.   1.   1.]</span>
<span class="s1"> [ 50.   1.   0.   0.  -1.]]</span>
<span class="s1">&#39;&#39;&#39;</span></code></pre></div>
<h2 id="section-3">复杂度分析</h2>
<p>Simplex 算法再单次约束计算中是否十分高效呢，我们来讨论一下其复杂度。</p>
<p>若对于一个 $m\times n$ 的矩阵来说，我们所有的时间开销均再以下三个点:</p>
<ol>
  <li>每次需要查找在目标方程中的一个负数 <code>O(n)</code>；</li>
  <li>每次需要查找对应项方程 <code>O(m)</code>；</li>
  <li>旋转操作中，每次需要执行 <code>mat[i] = mat[i] - mat[row] * mat[i][col]</code>。这个操作是对整个行进行操作，并且是按列下标遍历。<code>np.arrange</code> 操作每次会将行列扩展，我们将行定义为最大阈值 <code>m+n</code>，所以旋转开销 <code>O(m*(m+n)) = O(mN)</code>；</li>
</ol>
<p>当然这只是一次 <em>Simplex</em> 算法索要执行的时间开销。假设需要运行 <code>k</code> 次，则一次 <em>Simplex</em> 的时间复杂度为 <code>O(kmN)</code>。</p>
<h2 id="section-4">总结</h2>
<p>这里我们不得不说 WWDC 2018 - 202 中对于 AutoLayout 复杂度的图示：</p>
<p><img src="../assets/images/blog/15272074383889/15306636723931.jpg" alt="" /></p>
<p>虽然 <em>Simplex</em> 无论从我们上方的推导 <code>O(kmN)</code> 还是论文 <em><a href="http://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf">Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time</a></em> 里的论证，关于线性规划问题都会是一个<strong>多项式时间</strong>的复杂度。但是到目前为止，我们没有讨论任何增加一个新的约束之后与之前线性复杂度的开销对比。但是从直观计算上来讲，多了一个约束意味着纬度 <code>m</code> 和 <code>n</code> 均可能增大。那么说明当前场景下真实的<strong>多项式复杂度增量次幂并不为 1</strong>。那么，Apple 此次的优化是否是一次突破性的提升，还是修复了阿三之前的 Bug，还不能给出确定的结论。</p>
<p>这次的 <em>Simplex</em> 算法对于线性规划问题的 AutoLayout 问题只是最原始的算法基础。线性约束算法还有很多值得探究的算法，例如 <em>Cassowary</em>、<em>QOCA</em> 等等。后续将会做进一步的分析和学习。</p>
<h2 id="reference">Reference</h2>
<ul>
  <li><a href="http://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf">Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time</a></li>
  <li><a href="http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Lec8.pdf">CS711008Z Algorithm Design and Analysis Lecture 8. Algorithm design technique: Linear programming</a></li>
  <li><a href="Solving Linear Arithmetic Constraints for User Interface Applications">https://constraints.cs.washington.edu/solvers/uist97.pdf</a></li>
</ul>
  <footer class="post-footer">
    <section class="author">
      <h4>Desgard_Duan</h4>
      <p>I write many code to write less code.💻</p>
    </section>
<aside class="share">
  <h4>Share this.</h4>
  <a href="http://twitter.com/share?text=《AutoLayout 中的线性规划 - Simplex 算法》 -- Guardia · 瓜地&amp;url=https://www.desgard.com/autolayout-simplex/"
  onclick="window.open(this.href, 'twitter-share', 'width=550,height=235');return false;">
    <i class="fa fa-twitter-square"></i>
  </a>
  <a href="http://v.t.sina.com.cn/share/share.php?url=https://www.desgard.com/autolayout-simplex/&amp;title=《AutoLayout 中的线性规划 - Simplex 算法》 —— Guardia · 瓜地" onclick="window.open(this.href, 'twitter-share', 'width=550,height=235');return false;">
    <i class="fa fa-weibo"></i>
  </a>
</aside>
      <hr>
<aside id="comments" class="disqus">
  <div id="container"></div>
  <!-- <link rel="stylesheet" href="/assets/css/gitment.css">
  <script src="https://imsun.github.io/gitment/dist/gitment.browser.js"></script>
  <script>
  var gitment = new Gitment({
    id: "https://www.desgard.com/autolayout-simplex/", 
    owner: 'Desgard',
    repo: 'desgard.github.com',
    oauth: {
      client_id: 'e2612df42f3f2a83e71c',
      client_secret: 'b53e85b314bb24a6d06773e48bbb62a4de3b8b3a',
    },
  })
  gitment.render('container')
  </script> -->
<link rel="stylesheet" href="/assets/css/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>
<div id='gitalk-container'></div>
<script>
    const gitalk = new Gitalk({
        id: "https://www.desgard.com/autolayout-simplex/", 
        clientID: 'e2612df42f3f2a83e71c',
        clientSecret: 'b53e85b314bb24a6d06773e48bbb62a4de3b8b3a',
        repo: 'desgard.github.com',
        owner: 'Desgard',
        admin: ['Desgard'],
        // facebook-like distraction free mode
        distractionFreeMode: false
    })
    gitalk.render('gitalk-container')
</script>
</aside>
  </footer>
</article>
    </main>
<footer class="footer">
  <div class="container">
    <ul class="icons">
      <li>
        <a href="https://github.com/desgard" class="icon-github" target="_blank">
          <i class="fa fa-github"></i>
        </a>
      </li>
      <li>
        <a href="https://www.facebook.com/desgard.duan" class="icon-facebook" target="_blank">
          <i class="fa fa-facebook"></i>
        </a>
      </li>
      <li>
        <a href="https://twitter.com/Desgard_Duan" class="icon-twitter" target="_blank">
          <i class="fa fa-twitter"></i>
        </a>
      </li>
      <li>
        <a href="https://stackoverflow.com/users/6119149/desgard-duan" class="icon-github" target="_blank">
          <i class="fa fa-stack-overflow"></i>
        </a>
      </li>
      <li>
        <a href="https://weibo.com/desgard" class="icon-instagram" target="_blank">
          <i class="fa fa-weibo"></i>
        </a>
      </li>
    </ul>
    <p>
      <q>I write many code to write less code.💻</q>
      <small>– Gua</small>
    </p>
    <small class="clearfix">
      Powered by <a href="http://jekyllrb.com" target="_blank">Jekyll</a> • <a href="https://github.com/desgard" target="_blank">Open source <i class="fa fa-heart"></i></a>
    </small>
  </div>
</footer>
<a class="scroll-up fa fa-chevron-up bounce" href="#" data-position="0"></a>
<div id="modalSearch" class="modal">
  <div class="modal__overlay"></div>
  <div class="modal__content">
    <a href="#!" class="modal-close" data-modal-close>&times;</a>
    <div class="search-container">
      <input type="text" id="search-input" placeholder="Search articles">
      <ul id="results-container"></ul>
    </div>
  </div>
</div>
    <script src="/assets/main-52d417e8a6ff9f5b168386d37c96338a.js"></script>
  </body>
  <script>
    var link = "" ;
    var os = function() {  
      var ua = navigator.userAgent,  
      isWindowsPhone = /(?:Windows Phone)/.test(ua),  
      isSymbian = /(?:SymbianOS)/.test(ua) || isWindowsPhone,   
      isAndroid = /(?:Android)/.test(ua),   
      isFireFox = /(?:Firefox)/.test(ua),   
      isChrome = /(?:Chrome|CriOS)/.test(ua),  
      isTablet = /(?:iPad|PlayBook)/.test(ua) || (isAndroid && !/(?:Mobile)/.test(ua)) || (isFireFox && /(?:Tablet)/.test(ua)),  
      isPhone = /(?:iPhone)/.test(ua) && !isTablet,  
      isPc = !isPhone && !isAndroid && !isSymbian;  
      return {  
        isTablet: isTablet,  
        isPhone: isPhone,  
        isAndroid : isAndroid,  
        isPc : isPc  
      };  
    }();  
    if (link.length > 0) {
      if (os.isAndroid || os.isPhone) {
        location.replace(link);
      }
    }
  </script>
</html>